def sum_of_dig(n):
    if n < 10:
        return n
    else :
        all_but_last, last = n // 10, n % 10
        return sum_of_dig(all_but_last) + last
    

n = int(input("请输入一个整数"))
# print(sum_of_dig(n))

def factor(n):
    if n == 1:
        return n
    else:
        return factor(n-1)*n
        
# print(factor(n))
        
def is_odd(n):
    if n == 0:
        return False
    else:
        return is_even(n-1)
    
def is_even(n):
    if n == 0:
        return True
    else:
        return is_odd(n-1)

# print(is_odd(n))

def cascade(n):
    """Print a cascade of prefixes of n."""
    if n < 10:
        print(n)
    else:
        print(n)
        cascade(n//10)
        print(n)
        
cascade(n)

def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)
    
print(fib(n))